package com.zlk.algorithm.algorithm.unionAndFind;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: algorithm
 * @ClassName NumberOfIslandsII
 * @description:动态岛问题
 * 给定三个参数https://leetcode.cn/problems/number-of-islands-ii/description/
 *  矩阵  m n  = （3，3）
 *  位置  pos[{0,0},{0,1},{1,2},{2,1}] 意思是 依次{0,0},{0,1},{1,2},{2,1} 位置变成1 求岛数量
 *  每遍历到一个位置求岛数量
 *  动态岛问题
 *
 * @author: slfang
 * @create: 2024-03-13 16:46
 * @Version 1.0
 **/
public class NumberOfIslandsII {

    public  List<Integer> numIslands21(int m, int n, int[][] positions) {
        UnionFind1 uf = new UnionFind1(m, n);
        List<Integer> ans = new ArrayList<>();
        for (int[] position : positions) {
            ans.add(uf.connect(position[0], position[1]));
        }
        return ans;
    }


    class UnionFind1{
        int []parent;
        int []size;
        private int sets;
        int []help;
        private final int row;
        private final int col;

        public UnionFind1(int m,int n){
            row = m;
            col = n;
            sets = 0;
            int len = row * col;
            parent = new int[len];
            size = new int[len];
            help = new int[len];
        }
        public int connect(int r, int c) {
            int index = indexOf(r, c);
            if (size[index] == 0) {//数组可能存在重复的位置
                parent[index] = index;
                size[index] = 1;
                sets++;
                union(r - 1, c, r, c);
                union(r + 1, c, r, c);
                union(r, c - 1, r, c);
                union(r, c + 1, r, c);
            }
            return sets;
        }

        public void union(int r1, int c1, int r2, int c2) {
            if (r1 < 0 || r1 == row || r2 < 0 || r2 == row || c1 < 0 || c1 == col || c2 < 0 || c2 == col) {
                return;
            }
            int indexA = indexOf(r1, c1);
            int indexB = indexOf(r2, c2);
            int parentA = findParent(indexA);
            int parentB = findParent(indexB);
            if(parentA!=parentB){
                if(size[parentA]>=size[parentB]){
                    size[parentA]+=size[parentB];
                    parent[indexB] = parentA;
                }else{
                    size[parentB]+=size[parentA];
                    parent[indexA] = parentB;
                }
                sets--;
            }
        }

        private int findParent(int i) {
            int count = 0;
            while (i!=parent[i]){
                help[count++] = i;
                i = parent[i];
            }
            count--;
            while (count>=0){
                help[count--]=i;
            }
            return i;
        }

        public int sets(){
            return sets;
        }

        public int indexOf(int r,int c){
            return col*r+c;
        }

    }

    // 课上讲的如果m*n比较大，会经历很重的初始化，而k（位置数组的长度）比较小，怎么优化的方法  todo
    // 分治场景 todo





}
